package com.daydayup.homework;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给出一个数字S，以及一个数组a1...an，要求列出所有S=a1*x1+a2*x2+...+an*xn的所有组合，其中，xn>=0，a1...an均为正数
 * 。示例：输入，S=5，a1=3,a2=2,a3=1，输出，5=1*5,5=2*1+1*3,5=2*2+1*1,5=3*1+1* 2,5=3*1+2*1
 * 
 * @author Administrator
 *
 */
public class ArrayOperation {
	private static final int[] DATA = { 3, 2, 1 };
	private static final int SUM = 5;

	/**
	 * 循环将每个和及乘法式子放入Map集合
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		List<Map<String, Integer>> list = new ArrayList<Map<String, Integer>>();
		for (int i = 0; i < DATA.length; i++) {
			Map<String, Integer> multiplys = new HashMap<String, Integer>();
			for (int j = 0;; j++) {
				int multiply = DATA[i] * j;
				if (multiply > SUM) {
					break;
				}
				String formula = DATA[i] + "*" + j;
				multiplys.put(formula, multiply);
			}
			list.add(multiplys);
		}
		System.out.println(list);
		GetAllSubset example = new GetAllSubset(SUM);
		example.populateSubset(list, 0, DATA.length);
	}

}
